/**
 * @Author ZhangCuirong
 * @Date 2025/9/18 16:40
 * @description:
 */
public class Solution329 {
    int[][] memo;
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int longestIncreasingPath(int[][] matrix) {
        memo = new int[matrix.length][matrix[0].length];
        int max = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                max = Math.max(max, dp(matrix,i,j));
            }
        }
        return max;
    }

    public int dp(int[][] matrix, int i, int j) {
        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        int max = 1;//递增路径长度至少为 1，即自身
        for (int k = 0; k < 4; k++) {
            int nextX = i + dirs[k][0];
            int nextY = j + dirs[k][1];
            if (nextX >= 0 && nextX < matrix.length && nextY >= 0 && nextY < matrix[0].length) {
                if (matrix[nextX][nextY] > matrix[i][j]) {
                    // 从 (i, j) 出发的最长递增路径 = max(从四个相邻位置出发的最长递增路径的最大值 + 1)
                    max = Math.max(max, 1 + dp(matrix, nextX, nextY));
                }
            }
        }
        memo[i][j] = max;
        return max;
    }

    public static void main(String[] args) {
        Solution329 solution = new Solution329();
        System.out.println(solution.longestIncreasingPath(new int[][]{{9, 9, 4}, {6, 6, 8}, {2, 1, 1}}));
        System.out.println(solution.longestIncreasingPath(new int[][]{{3, 4, 5}, {3, 2, 6}, {2, 2, 1}}));
        System.out.println(solution.longestIncreasingPath(new int[][]{{1}}));
    }
}
